package com.zyk.leetcode;

import java.util.Arrays;

/**
 * @author zhangsan
 * @date 2021/4/26 20:33
 */
public class C31 {

    // 算法流程:
    // 找到下一个序列, 如果是最大的序列返回最小的序列
    // 从右边往左找到非升序的 下标, 他代表较小元素.
    // 再从有往左找到, 第一个比他大的元素, 即比较小元素要大的
    // 然后它两个交换位置, 在对后边进行反转. 因为前边寻找的过程是从小到大的.所以这段数字是有顺序的.
    // 如果从右往左全是升序, 即代表最大序列, 最小序列为所有元素反转
    public static void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1])     // 找到较小元素, 或为0
            i--;
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[j] <= nums[i]) j--;    // 找到比较小元素大的较大元素
            nums[i] = nums[i] ^ nums[j];    // 它两个交换位置
            nums[j] = nums[i] ^ nums[j];
            nums[i] = nums[i] ^ nums[j];
        }
        // 反转从i,开始反转数组
        i++;
        int j = nums.length - 1;
        for (; i < j; i++, j--) {
            nums[i] = nums[i] ^ nums[j];    // 它两个交换位置
            nums[j] = nums[i] ^ nums[j];
            nums[i] = nums[i] ^ nums[j];
        }
    }

    // for test
    public static void main(String[] args) {
        int[] nums = {1, 2};
        nextPermutation(nums);
        System.out.println(Arrays.toString(nums));

    }

}
